#include <iostream>

using namespace std;


struct TreeNode
{
    int val;
    TreeNode *right;
    TreeNode *left;
};
void preOrderTraverase(TreeNode *t);
void insertTreeNode(TreeNode **t, int data);


//-------------核心代码---------------
TreeNode* invertTree(TreeNode *t)
{
    if(t == NULL)
        return t;
    else
    {
        // if(t->left->val < t->right->val) //删去词句。想一想?
        {
            TreeNode *tmp;
            tmp = t->left;
            t->left = t->right;
            t->right = tmp;
        }
        invertTree(t->left);
        invertTree(t->right);
    }
    return t;
}


int main()
{
    TreeNode *root = NULL;
    
    int n = 7;
    //    cin>>n; //结点个数
    
    
    while(n--)
    {
        int data;
        cin>>data;
        insertTreeNode(&root,data);
    }
    preOrderTraverase(root);
    cout<<"=================="<<endl;
    invertTree(root);
    preOrderTraverase(root);
    return 0;
}

//有序递归插入
void insertTreeNode(TreeNode **t, int data)
{
    if((*t) == NULL)
    {
        (*t) = new TreeNode;
        (*t)->val = data;
        (*t)->left = (*t)->right = NULL;
    }
    else if(data > (*t)->val)
    {
        insertTreeNode(&((*t)->right),data);
    }
    else
        insertTreeNode(&((*t)->left),data);
}

//递归前序输出
void preOrderTraverase(TreeNode *t)
{
    if(t)
    {
        cout<<t->val<<endl;
        preOrderTraverase(t->left);
        preOrderTraverase(t->right);
    }
}